#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int lenOfVDiagonal(vector<vector<int>> &grid)
    {
        int n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>> single(
            n,
            vector<vector<int>>(
                m, vector<int>(4, 0)));
        int direct[4][2] = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
        auto nextNum = [](int num)
        {
            if (num == 2)
                return 0;
            if (num == 1 || num == 0)
                return 2;
            assert(false);
        };
        for (int d = 0; d < 4; ++d)
        {
            int dx = direct[d][0], dy = direct[d][1];
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < m; ++j)
                {
                    if (single[i][j][d])
                        continue;
                    int cur = grid[i][j];
                    int ni = i + dx, nj = j + dy;
                    stack<pair<int, int>> st;
                    st.push({i, j});
                    int cnt = 0;
                    while (ni >= 0 && ni < n && nj >= 0 && nj < m &&
                           nextNum(cur) == grid[ni][nj])
                    {
                        if (single[ni][nj][d])
                        {
                            cnt = single[ni][nj][d];
                            break;
                        }
                        st.push({ni, nj});
                        cur = grid[ni][nj];
                        ni = ni + dx;
                        nj = nj + dy;
                    }
                    while (!st.empty())
                    {
                        auto p = st.top();
                        st.pop();
                        ++cnt;
                        int x = p.first, y = p.second;
                        single[x][y][d] = cnt;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] != 1)
                    continue;
                for (int d = 0; d < 4; ++d)
                {
                    int dx = direct[d][0], dy = direct[d][1];
                    ans = max(ans, single[i][j][d]);
                    int l = 1;
                    int nd = (d + 1) % 4;
                    for (int ni = i + dx, nj = j + dy; l < single[i][j][d]; ++ni, ++nj, ++l)
                    {
                        ans = max(ans, l + single[ni][nj][nd]);
                    }
                }
            }
        }
        return ans;
    }
};

int main()
{

    // system("pause");
    return 0;
}
